/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:38917
 * Date:2025/4/6
 * Time:18:24
 */
public class Solution {
    /*public int maxSubArray(int[] nums) {
        //初始化最大值是0为下标的元素
        int maxSum = nums[0];
        //初始化子数组和为0
        int sum = 0;
        for (int cur : nums) {
            //当sum>0时,说明sum对结果有增益效果,应该保留sum值并且加上当前遍历元素
            //因为sum是>0的,cur是多大不确定,所以让sum+cur有可能会得到一个更大的值
            //即便cur<0,下面的Math.max函数依旧能保存sum+cur之前的值
            if (sum > 0) {
                sum += cur;
            }else {
                //当sum<=0时,说明sum对结果没有增益效果,应该放弃,将sum更新为当前遍历的元素cur
                //因为sum<=0，所以不论cur值是多少,sum+cur一定是<=sum的,所以直接将sum更新为cur
                sum = cur;
            }
            maxSum = Math.max(maxSum, sum);
        }
        return maxSum;
    }*/
    public int maxSubArray(int[] nums) {
        int length = nums.length;
        int[] dp = new int[length + 1];
        int result = Integer.MIN_VALUE;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = Math.max(nums[i - 1] + dp[i - 1], nums[i - 1]);
            result = Math.max(result, dp[i]);
        }
        return result;
    }
    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        Solution solution = new Solution();
        int ret = solution.maxSubArray(nums);
        System.out.println(ret);
    }
}